<!DOCTYPE html>
<html lang="en">
<head>
	<meta charset="UTF-8">
	<title>硬币找零问题</title>
</head>
<body>
	<script>
	function findCoins(coins, amount) {
	  if (coins.length === 0) return -1;
	  // 用于保存每个目标总额对应的最小硬币个数
	  const f = [];
	  // 提前定义已知情况
	  f[0] = 0;
	  // 遍历 [1, amount] 这个区间的硬币总额
	  for (let i = 1; i <= amount; i++) {
	    // 求的是最小值，因此我们预设为无穷大，确保它一定会被更小的数更新
	    f[i] = Infinity;
	    // 循环遍历每个可用硬币的面额
	    for (let j = 0; j < coins.length; j++) {
	      // 若硬币面额小于目标总额，则问题成立
	      if (i - coins[j] >= 0) {
	        // 状态转移方程
	        if (i === 23) {
	        	console.log(j, coins[j], f[i], f[i - coins[j]] + 1)
	        }
	        f[i] = Math.min(f[i], f[i - coins[j]] + 1);
	      }
	    }
	  }
	  // 若目标总额对应的解为无穷大，则意味着没有一个符合条件的硬币总数来更新它，本题无解，返回-1
	  if (f[amount] === Infinity) {
	    return -1;
	  }
	  // 若有解，直接返回解的内容
	  return f[amount];
	}

	console.log(findCoins([3, 4, 6], 23)); // 3

	/**
	 * 解题思路，对amount的值从0到amount遍历，遍历每个金额所存在的可能
	 * 上面金额是 23
	 * 金币面额是 [3,4,6]
	 * 23 - 6（金币最大值）= 17
	 * 在查 组合17需要多少个硬币
	 * 17 - 6 = 11
	 * 在查 组合11需要多少个硬币
	 * 11 - 6 = 5(明显组合5的不存在)
	 * 11 - 4 = 7 
	 * 在查 组合7需要多少个硬币
	 * 7 - 6 = 1(明显组合1的不存在)
	 * 7 - 4 = 3
	 *
	 * 很明显 组合 7是2个
	 * f[7] = 2
	 * f[11] = 2 + 1 = 3 注意上面的逻辑 f[i - coins[j]] + 1
	 * f[17] = 4
	 * f[23] = 5
	 */
	</script>
</body>
</html>